home *** CD-ROM | disk | FTP | other *** search
/ EuroCD 3 / EuroCD 3.iso / Programming / Python1.4_Source / Lib / zmod.py < prev   
Text File  |  1998-06-24  |  2KB  |  95 lines
  1. # module 'zmod'
  2.  
  3. # Compute properties of mathematical "fields" formed by taking
  4. # Z/n (the whole numbers modulo some whole number n) and an 
  5. # irreducible polynomial (i.e., a polynomial with only complex zeros),
  6. # e.g., Z/5 and X**2 + 2.
  7. #
  8. # The field is formed by taking all possible linear combinations of
  9. # a set of d base vectors (where d is the degree of the polynomial).
  10. #
  11. # Note that this procedure doesn't yield a field for all combinations
  12. # of n and p: it may well be that some numbers have more than one
  13. # inverse and others have none.  This is what we check.
  14. #
  15. # Remember that a field is a ring where each element has an inverse.
  16. # A ring has commutative addition and multiplication, a zero and a one:
  17. # 0*x = x*0 = 0, 0+x = x+0 = x, 1*x = x*1 = x.  Also, the distributive
  18. # property holds: a*(b+c) = a*b + b*c.
  19. # (XXX I forget if this is an axiom or follows from the rules.)
  20.  
  21. import poly
  22.  
  23.  
  24. # Example N and polynomial
  25.  
  26. N = 5
  27. P = poly.plus(poly.one(0, 2), poly.one(2, 1)) # 2 + x**2
  28.  
  29.  
  30. # Return x modulo y.  Returns >= 0 even if x < 0.
  31.  
  32. def mod(x, y):
  33.     return divmod(x, y)[1]
  34.  
  35.  
  36. # Normalize a polynomial modulo n and modulo p.
  37.  
  38. def norm(a, n, p):
  39.     a = poly.modulo(a, p)
  40.     a = a[:]
  41.     for i in range(len(a)): a[i] = mod(a[i], n)
  42.     a = poly.normalize(a)
  43.     return a
  44.  
  45.  
  46. # Make a list of all n^d elements of the proposed field.
  47.  
  48. def make_all(mat):
  49.     all = []
  50.     for row in mat:
  51.         for a in row:
  52.             all.append(a)
  53.     return all
  54.  
  55. def make_elements(n, d):
  56.     if d == 0: return [poly.one(0, 0)]
  57.     sub = make_elements(n, d-1)
  58.     all = []
  59.     for a in sub:
  60.         for i in range(n):
  61.             all.append(poly.plus(a, poly.one(d-1, i)))
  62.     return all
  63.  
  64. def make_inv(all, n, p):
  65.     x = poly.one(1, 1)
  66.     inv = []
  67.     for a in all:
  68.         inv.append(norm(poly.times(a, x), n, p))
  69.     return inv
  70.  
  71. def checkfield(n, p):
  72.     all = make_elements(n, len(p)-1)
  73.     inv = make_inv(all, n, p)
  74.     all1 = all[:]
  75.     inv1 = inv[:]
  76.     all1.sort()
  77.     inv1.sort()
  78.     if all1 == inv1: print 'BINGO!'
  79.     else:
  80.         print 'Sorry:', n, p
  81.         print all
  82.         print inv
  83.  
  84. def rj(s, width):
  85.     if type(s) <> type(''): s = `s`
  86.     n = len(s)
  87.     if n >= width: return s
  88.     return ' '*(width - n) + s
  89.  
  90. def lj(s, width):
  91.     if type(s) <> type(''): s = `s`
  92.     n = len(s)
  93.     if n >= width: return s
  94.     return s + ' '*(width - n)
  95.